/*
day117
2019.12.23
*/
#include<iostream>
#include<vector>
#include<cmath> 
using namespace std;

class Solution {
public:
    int mySqrt(int x) {
//    	cout<<sqrt(2147483647)<<endl;
        int l=0,r=x;
        
        int mid=0;
        
        while(l<r)
        {
//        	cout<<l<<'\t'<<r<<endl;
        	
        	mid=l+(r-l)/2;
        	
        	if( mid > 46341 ) 
			{
				r=mid;
				continue;
			}
        	
        	int res=mid*mid;
        	
        	if(res==x) return mid;
        	
        	else if(res<x) l=mid+1;
        	
        	else r=mid;
		}
		
		if(l>=46341 || l*l > x) return l-1;
		
		else return l;
    }
};


int main()
{
	Solution s;
	s.mySqrt(1) ;
	return 0;
}
